//给你一个字符串 s，找到 s 中最长的回文子串。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "babad"
//输出："bab"
//解释："aba" 同样是符合题意的答案。
// 
//
// 示例 2： 
//
// 
//输入：s = "cbbd"
//输出："bb"
// 
//
// 示例 3： 
//
// 
//输入：s = "a"
//输出："a"
// 
//
// 示例 4： 
//
// 
//输入：s = "ac"
//输出："a"
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 1000 
// s 仅由数字和英文字母（大写和/或小写）组成 
// 
// Related Topics 字符串 动态规划 
// 👍 3836 👎 0

import java.util.*;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution5 {

    public String longestPalindrome(String s) {
        int max = 1;
        int start = 0;
        int n = s.length();
        boolean[][] res = new boolean[n][n]; // res[j][i]表示从j到i字符是否回文；

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j <= i; ++j) {
                res[j][i] = (i - j < 2) ? s.charAt(i) == s.charAt(j) :
                        (res[j+1][i-1] && s.charAt(i) == s.charAt(j));

                // res[0][3] : res[1][2]

                if (res[j][i] && max <= i -j + 1){
                    max = i -j + 1;
                    start = j;
                }
            }
        }
        return s.substring(start, start + max);
    }
}
//leetcode submit region end(Prohibit modification and deletion)
